The present invention relates to the field of integrated circuit design. More particularly, the present invention relates to a placement algorithm such as may be used for large-scale standard cell designs.
Placement happens to be one of the most persistent challenges in present day Integrated Circuit design. Designs in current deep sub-micron technology often contain over a million placeable components, and are getting larger by the day. Moreover, because of the dominance of interconnect delay, placement has become a major contributor to timing closure results. Placement needs to be performed early in the design flow. Hence, it becomes imperative to have an ultra-fast placement tool to handle the ever increasing placement problem size.
In recent years, many placement algorithms have been proposed to handle the widely-used objective of wire length minimization. These algorithms apply various approaches including analytical placement, simulated annealing, and partitioning/clustering. Analytical placement is the most promising approach for fast placement algorithm design. Analytical placement algorithms commonly utilize a quadratic wire length objective function. Although the quadratic objective is only an indirect measure of the wire length, its main advantage is that it can be minimized quite efficiently. As a result, analytical placement algorithms are relatively efficient in handling large problems. They typically employ a flat methodology so as to maintain a global view of the placement problem. For simulated annealing and partitioning/clustering based approaches, a hierarchical methodology is almost always employed to reduce the problem size to speed up the resulting algorithms. Note that, when the placement problem is so large that a flat analytical approach cannot handle it effectively, a hierarchical analytical approach is beneficial. One of the methods to convert to a hierarchical approach is by incorporating the fine granularity clustering technique proposed by Hu et al. This technique essentially introduces a two-level hierarchy to reduce the size of large-scale placement problems.
A major concern with the quadratic objective is that it results in a placement with a large amount of overlap among cells. Also, the quadratic objective by itself does not give the best possible wire length. To handle these problems, Klein-hans et al., use a placement-based bisection technique to recursively divide the circuit and add linear constraints to pull the cells in each partition to the center of the corresponding region. The FM min-cut algorithm is used to improve the bisection and hence the wire length. Vygen applies a position-based quadrisection technique instead. A splitting-up technique to modify the net list is also proposed to ensure that the cells will stay in the assigned region. The splitting-up technique also breaks down long nets and hence makes the objective behave like a linear function to some extent. Eisenmann et al. introduces additional constant forces to each cell based on cell distribution to pull cells away from dense regions. Etawil et al. adds repelling forces for cells sharing a net to maintain a target distance between them and attractive forces by fixed dummy cells to pull cells from dense to sparse regions. Hu et al. introduces the idea of fixed-point as a more general way to add forces for cell spreading. The last three references mainly focus on cell spreading. They have not discussed ways to improve the wire length by a quadratic objective.
Thus, despite various attempts and approaches at providing efficient analytical placement of cells in integrated circuit design, problems remain.